package backtrack;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;

/**
 * @author : Rookie
 * @description :
 * @date : 2023/6/27
 */
public class NQueen {

    public static void main(String[] args) {

        Scanner scanner = new Scanner(System.in);
        while (true) {
            System.out.print("请输入皇后个数：");
            String input = scanner.nextLine();
            int n = Integer.parseInt(input);
            char[][] chessboard = new char[n][n];
            for (char[] row : chessboard) {
                Arrays.fill(row, '0');
            }
            List<List<String>> result = new ArrayList<>();
            getSolve(0,chessboard,result);
            System.out.println(n + "皇后问题有" + result.size() + "种解法，分别是：");
            result.forEach(res -> {
                printResult(res);
                System.out.println();
            });
        }
    }

    private static void printResult(List<String> res) {
        res.forEach(System.out::println);
    }

    /**
     *
     * @param row
     * @param startIndex
     * @param chessBoard
     */
    private static void getSolve(int row, char [][]chessBoard, List<List<String>> result) {
        if (row == chessBoard.length) {
            // 能遍历到叶子节点 一定是合法的

            result.add(charArray2dToList(chessBoard));
            return;
        }

        for (int i = 0; i < chessBoard.length; i++) {
            if (isValid(row,i,chessBoard)) {
                chessBoard[row][i] = 'Q';
                getSolve(row + 1,chessBoard,result);
                chessBoard[row][i] = '0';
            }
        }
    }

    private static List<String> charArray2dToList(char [][]chessboard) {
        ArrayList<String> result = new ArrayList<>();
        for (char[] row : chessboard) {
            result.add(Arrays.toString(row));
        }
        return result;
    }

    private static boolean isValid(int row,int col,char [][]chessboard) {
        // 检查列
        for (int i = 0; i < row; i++) { // 这是一个剪枝
            if (chessboard[i][col] == 'Q') {
                return false;
            }
        }
        // 检查 45度角是否有皇后
        for (int i = row - 1, j = col - 1; i >=0 && j >= 0; i--, j--) {
            if (chessboard[i][j]=='Q') {
                return false;
            }
        }
        // 检查 135度角是否有皇后
        for(int i = row - 1, j = col + 1; i >= 0 && j < chessboard.length; i--, j++) {
            if (chessboard[i][j]=='Q') {
                return false;
            }
        }
        return true;
    }
}
